package com.jiang.daily.Q2537;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/04/16 15:14
 */
public class Solution {
    public long countGood(int[] nums, int k) {
        long res = 0;
        long good = 0;
        int len = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0, j = 0; i < len; i++) {
            int t = map.getOrDefault(nums[i], 0) + 1;
            map.put(nums[i], t);
            good = good - cal(t - 1) + cal(t);
            while (good >= k) {
                res += len - i;
                t = map.get(nums[j]) - 1;
                map.put(nums[j], t);
                good = good - cal(t + 1) + cal(t);
                j++;
            }
        }
        return res;
    }

    private long cal(int x) {
        return (long) x * (x - 1) / 2;
    }
}
